package T回溯;

import java.util.LinkedList;
import java.util.List;

/**
 * @author tmh
 * @date 2023/10/18 19:26
 * @description T_93复原IP地址
 * 跟切割字符串都是类似相同的模板套路，只是终止判断的逻辑不一样
 */
public class T_93复原IP地址 {
    LinkedList<String> result = new LinkedList<>();

    public List<String> restoreIpAddresses(String s) {
        if(s.length()>12){
            return result;
        }
        backTracking(s,0,0);
        return result;
    }

    private void backTracking(String s, int startIndex, int pointNum) {
        if (pointNum == 3) {
            if (isValid(s, startIndex, s.length() - 1)) {
                result.add(s);
            }
            return;
        }
        for (int i = startIndex; i < s.length() - 1; i++) {
            //startIndex~i就是我们要切割下来的字符串
            if (isValid(s, startIndex, i)) {
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);
                pointNum++;

                backTracking(s, i + 2, pointNum);
                //下面是进行回溯的过程
                s = s.substring(0, i + 1) + s.substring(i + 2);
                pointNum--;
            }
        }
    }

    // 判断字符串s在左闭⼜闭区间[start, end]所组成的数字是否合法
    private Boolean isValid(String s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法
            return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到⾮数字字符不合法
                return false;
            }
            num = num * 10 + (s.charAt(i) - '0');
            if (num > 255) { // 如果⼤于255了不合法
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        T_93复原IP地址 t = new T_93复原IP地址();
        List<String> list = t.restoreIpAddresses("25525511135");
        System.out.println(list);
    }
}
